package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.回溯;

import com.zp.self.module.level_4_算法练习.数据结构.链表.ListNode;

/**
 * @author By ZengPeng
 */
public class 力扣_206_反转链表 {
    //测试
    public static void main(String[] args) {
        ListNode node = ListNode.getNode();
        ListNode listNode = new 力扣_206_反转链表().reverseList3(node);
        System.out.println(listNode);
    }

    /**
     * 题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     *
     * 提示：
     * 链表中节点的数目范围是 [0, 5000]
     * -5000 <= Node.val <= 5000
     *
     * 进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
     *
     * 分析：【P 💕💞】
     * 1.常规方法：不断创建新节点 指向前面生成的节点
     * 2.递归： 单步操作，返回值 ，终止条件
     *          特殊的尾递归：在函数的最后: 返回递归调用函数，即返回最后一次递归调用返回的值。
     * 3.迭代方式：while  记录上一个节点，依次更新当前节点
     *  --执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
     *
     * 边界值注意：
     * 1.
     **/
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        ListNode next = head.next;
        head.next = null;
        return recursion(head, next);
    }

    private ListNode recursion(ListNode head, ListNode next) {
        if (next != null) {
            ListNode next1 = next.next;
            next.next = head;
            return recursion(next, next1);
        } else
            return head;
    }

    //3.3迭代方式：while 虚拟头节点
    public ListNode reverseList4(ListNode head) {
        if(head==null)return null;
        ListNode pro = new ListNode();//virtual 虚拟，但pro更好理解
        pro.next=head;
        ListNode currentNode = head;
        while (currentNode.next!=null){
            head = currentNode.next;//head其实是next
            currentNode.next=head.next;
            head.next=pro.next;//把虚拟头节点当前指向  ，给到新的节点.next
            pro.next = head;//更新虚拟节点.next
        }
        return pro.next;
    }


    //3.2迭代方式：while 记录前一个节点
    public ListNode reverseList3(ListNode head) {
        ListNode pro = null;
        ListNode currentNode = head;
        while (currentNode!=null){
            head = currentNode.next;
            currentNode.next=pro;
            pro=currentNode;
            currentNode = head;
        }
        return pro;
    }




    //3.1迭代方式：while  记录当前节点？
    public ListNode reverseList2(ListNode head) {
        ListNode currentNode = null;
        ListNode next = head;
        while (next != null) {
            ListNode next1 = next.next;
            next.next = currentNode;
            currentNode = next;
            next = next1;
        }
        return currentNode;
    }
}
